package main

func BubbleSort(arr []*Person) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j].fateRate > arr[j+1].fateRate {
				arr[j].fateRate, arr[j+1].fateRate = arr[j+1].fateRate, arr[j].fateRate
			}
		}
	}
}

func QuickSort(arr []*Person, start, end int) {
	pivotIdx := (start + end) / 2
	pivotV := arr[pivotIdx].fateRate
	l, r := start, end
	for l <= r {
		for arr[l].fateRate < pivotV {
			l++
		}
		for arr[r].fateRate > pivotV {
			r--
		}
		if l >= r {
			break
		}

		arr[l].fateRate, arr[r].fateRate = arr[r].fateRate, arr[l].fateRate
		l++
		r--
	}
	if l == r {
		l++
		r--
	}
	if r > start {
		QuickSort(arr, start, r)
	}
	if l < end {
		QuickSort(arr, l, end)
	}
}
